//: [Previous](@previous)
import Foundation

/*:
 斐波那契数列
 */

/*:
 1. 暴力递归
 存在大量重复计算(重叠子问题)
 */
func fib(_ num: Int) -> Int {
    if num == 1 || num == 2 {
        return 1
    }
    return fib(num - 1) + fib(num - 2)
}

print(fib(20))

/*:
 2. 带备忘录的递归解法
 自顶向下
 */

var memo: [Int: Int] = [:]
func fib2(_ num: Int) -> Int {
    if num == 1 || num == 2 {
        memo[num] = 1
        return 1
    }

    var num1: Int
    if memo[num - 1] != nil {
        num1 = memo[num - 1]!
    } else {
        num1 = fib(num - 1)
    }

    var num2: Int
    if memo[num - 2] != nil {
        num2 = memo[num - 2]!
    } else {
        num2 = fib(num - 2)
    }

    return num1 + num2
}
print(fib(20))

func fib3(_ num: Int) -> Int {
    if num < 1 {
        return 0
    }
    var nums: [Int] = Array.init(repeating: 0, count: num + 1)
    return helper(&nums, num)
}

func helper(_ nums: inout [Int], _ num: Int) -> Int {
    if num == 1 || num == 2 {
        return 1
    }
    if nums[num] != 0 {
        return nums[num]
    }
    nums[num] = helper(&nums, num - 1) + helper(&nums, num - 2)
    return nums[num]
}
print(fib3(20))

/*:
 3. dp 数组的迭代解法
 自底向上
 */
func fib4(_ num: Int) -> Int {
    var dp: [Int] = Array(repeating: 0, count: num + 1)
    dp[1] = 1
    dp[2] = 1
    for i in 3...num {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[num]
}
print(fib4(20))

func fib5(_ num: Int) -> Int {
    var prev = 1, cur = 1
    for _ in 3...num {
        let sum = prev + cur
        prev = cur
        cur = sum

    }
    return cur
}
print(fib4(20))

/*:
 状态方程
 1, n=1,2
 f(n-1)+f(n-2),n>2
 */

//: [Next](@next)
